High-Efficiency Video Coding (HEVC) is a new international video coding standard developed by the Joint Collaborative Team on Video Coding (JCT-VC). HEVC is based on the hybrid block-based motion-compensated DCT-like transform coding architecture. The basic unit for compression, termed coding unit (CU), is a 2N×2N square block. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC and each CU can be recursively split into four smaller CUs until the predefined minimum size is reached. Once the splitting of CU hierarchical tree is done, each CU is further split into one or more prediction units (PUs) according to prediction type and PU partition. Each CU or the residual of each CU is divided into a tree of transform units (TUs) to apply 2D transforms such as DCT (discrete cosine transform) or DST (discrete sine transform).
Like many other precedent standards, HEVC adopts Discrete Cosine Transform type II (DCT-II) as its core transform because it has a strong “energy compaction” property. Most of the signal information tends to be concentrated in few low-frequency components of the DCT-II, which approximates the Karhunen-Loève Transform (KLT). As known in the art, KLT is the optimal transform to de-correlate signals that can be modelled by Markov processes. The N-point DCT-II of the signal f[n] is defined in equation (1).
                                                                        f                ^                                            DCT                ⁢                                  -                                ⁢                II                                      ⁡                          [              k              ]                                =                                    λ              k                        ⁢                          2                              N                                      ⁢                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                f                  ⁡                                      [                    n                    ]                                                  ⁢                                  cos                  [                                                                                    k                        ⁢                                                                                                  ⁢                        π                                            N                                        ⁢                                          (                                              n                        +                                                  1                          2                                                                    )                                                        ]                                                                    ,                                  ⁢                  k          =          0                ,        1        ,        2        ,        …        ⁢                                  ,                  N          -          1                ,                                  ⁢                              λ            k                    =                      {                                                                                                                              2                                                  -                          0.5                                                                    ,                                                                                                  k                      =                      0                                                                                                                                  1                      ,                                                                                                  k                      ≠                      0                                                                                  .                                                          (        1        )            
For Intra-predicted residue, there are other transforms that are found to be more efficient than DCT-II. In JCTVC-B024 (Yeo, et al., “Mode Dependent Fast Separable KLT for Block-based Intra Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 2nd Meeting: Geneva, CH, 21-28 Jul. 2010, Document: JCTVC-B024), JCTVC-C108 (Saxena, et al., “Jointly optimal intra prediction and adaptive primary transform”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 3rd Meeting: Guangzhou, CN, 7-15 Oct. 2010, Document: JCTVC-C108) and JCTVC-E125 (Saxena, et al., “CE7: Mode-dependent DCT/DST without 4*4 full matrix multiplication for intra prediction”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 5th Meeting: Geneva, CH, 16-23 Mar. 2011, Document: JCTVC-E125), Discrete Sine Transform (DST) was introduced as an alternative to DCT for oblique Intra modes. For Inter-predicted residue, DCT-II is the only transform used in the current HEVC. However, the DCT-II is not the optimal transform for all cases. In JCTVC-G281 (An, et al., “Non-CE7: Boundary-Dependent Transform for Inter-Predicted Residue”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, Document: JCTVC-G281), the Discrete Sine Transform type VII (DST-VII) and Discrete Cosine Transform type IV (DCT-IV) are proposed to replace DCT-II in some cases. When using Inter prediction for a PU, the prediction error (i.e., prediction residue or residue) is usually larger near the PU boundaries than in the middle of the PU. FIG. 1 illustrates an example of the squared residue values for a 4×4 PU. As shown in FIG. 1, the residue (i.e., prediction error) tends to have larger squared values at the PU boundaries.
When a PU is split into multiple TUs as shown in FIG. 2, the prediction error is larger near PU boundaries than near interior TU (non-PU) boundaries. In FIG. 2, PU 210 is split into four TUs (i.e., TU0, TU1, TU2 and TU3). Block 220 corresponds to the squared residue values of the upper-left TU (i.e., TU0), where the residues near the PU boundaries (indicated by thick solid lines) are generally larger than the residues near the interior TU boundaries (indicated by dashed lines). For TU0, a trend can be observed that the squared residue values peak roughly around the upper-left corner and decrease toward the lower-right corner. Similarly, for other TUs, the squared residue values also peak roughly around the respective PU corners and decrease toward the center of the PU.
The reason of this effect may be due to the different motion vectors (MV) between two neighboring PUs. In order to handle this uneven error distribution, alternative transforms such as DST-VII and DCT-IV can be used. Equations (2) and (3) show the N-point DST-VII and DCT-IV of signal f[n], respectively.
                                                                        f                ^                                            DST                ⁢                                  -                                ⁢                VII                                      ⁡                          [              k              ]                                =                                    2                                                                    2                    ⁢                    N                                    +                  1                                                      ⁢                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                f                  ⁡                                      [                    n                    ]                                                  ⁢                sin                ⁢                                                                            (                                                                        2                          ⁢                          k                                                +                        1                                            )                                        ⁢                                          (                                              n                        +                        1                                            )                                        ⁢                    π                                                                              2                      ⁢                      N                                        +                    1                                                                                      ,                                  ⁢                  k          =          0                ,        1        ,        …        ⁢                                  ,                  N          -          1                ,                            (        2        )                                                                                    f                ^                                            DCT                ⁢                                  -                                ⁢                IV                                      ⁡                          [              k              ]                                =                                    2                              N                                      ⁢                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                f                  ⁡                                      [                    n                    ]                                                  ⁢                                  cos                  [                                                                                                                                                              ⁢                        π                                            N                                        ⁢                                          (                                              k                        +                                                  1                          2                                                                    )                                        ⁢                                          (                                              n                        +                                                  1                          2                                                                    )                                                        ]                                                                    ,                                  ⁢                  k          =          0                ,        1        ,        …        ⁢                                  ,                  N          -          1.                                    (        3        )            
Based on the above observation, a method is disclosed in JCTVC-G281 that uses DST-VII or DCT-IV instead of DCT-II if one and only one of the two TU boundaries in the horizontal or vertical direction is a PU boundary. Table 1 shows the mapping from boundary type to transform type by using the DST-VII. Table 2 shows the mapping from boundary type to transform by using the DCT-IV.
TABLE 1TU BoundaryHorizontalTU BoundaryVerticalLeftRightTrans.TopBottomTrans.non-PUPUDST-VIInon-PUPUDST-VIIPUnon-PUF(DST-VII)PUnon-PUF(DST-VII)PUPUDCT-IIPUPUDCT-IInon-PUnon-PUDCT-IInon-PUnon-PUDCT-II
TABLE 2TU BoundaryHorizontalTU BoundaryVerticalLeftRightTrans.TopBottomTrans.non-PUPUF(DCT-IV)non-PUPUF(DCT-IV)PUnon-PUDCT-IVPUnon-PUDCT-IVPUPUDCT-IIPUPUDCT-IInon-PUnon-PUDCT-IInon-PUnon-PUDCT-II
The F(DST-VII) in Table 1 means flipping the DST matrix from left to right. The cases of using F(DST-VII) can also be implemented as flipping the input data first and then using DST-VII. It is also the case for F(DCT-IV). In Table 1 and Table 2, the items “non-PU” and “PU” mean non-PU boundary and PU boundary, respectively. In Table 1 and Table 2, when both of the TU boundaries in the horizontal or vertical direction are PU boundary or a non-PU boundary, DCT-II is used.
According to the Table 1, the four TUs in FIG. 2 will use transforms as shown in Table 3.
TABLE 3HorizontalVerticalTUTrans.Trans.TU0F(DST-VII)F(DST-VII)TU1DST-VIIF(DST-VII)TU2F(DST-VII)DST-VIITU3DST-VIIDST-VII
The Boundary Dependent Transform (BDT) method disclosed in JCTVC-G281 may improve the overall performance of the coding system. However, due to the characteristics of individual TU or PU, the BDT method according to JCTVC-G281 may not always achieve the best performance for a given block. It is desirable to develop a method to further improve the performance.